(0) Obligation:
Runtime Complexity TRS:
The TRS R consists of the following rules:
a__a → a__c
a__b → a__c
a__c → e
a__k → l
a__d → m
a__a → a__d
a__b → a__d
a__c → l
a__k → m
a__A → a__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__A → A
a__a → a
a__b → b
a__c → c
a__d → d
a__k → k
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)
Rewrite Strategy: FULL
(1) RenamingProof (EQUIVALENT transformation)
Renamed function symbols to avoid clashes with predefined symbol.
(2) Obligation:
Runtime Complexity Relative TRS:
The TRS R consists of the following rules:
a__a → a__c
a__b → a__c
a__c → e
a__k → l
a__d → m
a__a → a__d
a__b → a__d
a__c → l
a__k → m
a__A → a__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__A → A
a__a → a
a__b → b
a__c → c
a__d → d
a__k → k
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)
S is empty.
Rewrite Strategy: FULL
(3) TypeInferenceProof (BOTH BOUNDS(ID, ID) transformation)
Infered types.
(4) Obligation:
TRS:
Rules:
a__a → a__c
a__b → a__c
a__c → e
a__k → l
a__d → m
a__a → a__d
a__b → a__d
a__c → l
a__k → m
a__A → a__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__A → A
a__a → a
a__b → b
a__c → c
a__d → d
a__k → k
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)
Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g
(5) OrderProof (LOWER BOUND(ID) transformation)
Heuristically decided to analyse the following defined symbols:
a__A,
a__h,
a__f,
a__g,
mark,
a__zThey will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z
(6) Obligation:
TRS:
Rules:
a__a →
a__ca__b →
a__ca__c →
ea__k →
la__d →
ma__a →
a__da__b →
a__da__c →
la__k →
ma__A →
a__h(
a__f(
a__a),
a__f(
a__b))
a__h(
X,
X) →
a__g(
mark(
X),
mark(
X),
a__f(
a__k))
a__g(
d,
X,
X) →
a__Aa__f(
X) →
a__z(
mark(
X),
X)
a__z(
e,
X) →
mark(
X)
mark(
A) →
a__Amark(
a) →
a__amark(
b) →
a__bmark(
c) →
a__cmark(
d) →
a__dmark(
k) →
a__kmark(
z(
X1,
X2)) →
a__z(
mark(
X1),
X2)
mark(
f(
X)) →
a__f(
mark(
X))
mark(
h(
X1,
X2)) →
a__h(
mark(
X1),
mark(
X2))
mark(
g(
X1,
X2,
X3)) →
a__g(
mark(
X1),
mark(
X2),
mark(
X3))
mark(
e) →
emark(
l) →
lmark(
m) →
ma__A →
Aa__a →
aa__b →
ba__c →
ca__d →
da__k →
ka__z(
X1,
X2) →
z(
X1,
X2)
a__f(
X) →
f(
X)
a__h(
X1,
X2) →
h(
X1,
X2)
a__g(
X1,
X2,
X3) →
g(
X1,
X2,
X3)
Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g
Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)
The following defined symbols remain to be analysed:
a__h, a__A, a__f, a__g, mark, a__z
They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z
(7) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)
Could not prove a rewrite lemma for the defined symbol a__h.
(8) Obligation:
TRS:
Rules:
a__a →
a__ca__b →
a__ca__c →
ea__k →
la__d →
ma__a →
a__da__b →
a__da__c →
la__k →
ma__A →
a__h(
a__f(
a__a),
a__f(
a__b))
a__h(
X,
X) →
a__g(
mark(
X),
mark(
X),
a__f(
a__k))
a__g(
d,
X,
X) →
a__Aa__f(
X) →
a__z(
mark(
X),
X)
a__z(
e,
X) →
mark(
X)
mark(
A) →
a__Amark(
a) →
a__amark(
b) →
a__bmark(
c) →
a__cmark(
d) →
a__dmark(
k) →
a__kmark(
z(
X1,
X2)) →
a__z(
mark(
X1),
X2)
mark(
f(
X)) →
a__f(
mark(
X))
mark(
h(
X1,
X2)) →
a__h(
mark(
X1),
mark(
X2))
mark(
g(
X1,
X2,
X3)) →
a__g(
mark(
X1),
mark(
X2),
mark(
X3))
mark(
e) →
emark(
l) →
lmark(
m) →
ma__A →
Aa__a →
aa__b →
ba__c →
ca__d →
da__k →
ka__z(
X1,
X2) →
z(
X1,
X2)
a__f(
X) →
f(
X)
a__h(
X1,
X2) →
h(
X1,
X2)
a__g(
X1,
X2,
X3) →
g(
X1,
X2,
X3)
Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g
Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)
The following defined symbols remain to be analysed:
a__g, a__A, a__f, mark, a__z
They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z
(9) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)
Could not prove a rewrite lemma for the defined symbol a__g.
(10) Obligation:
TRS:
Rules:
a__a →
a__ca__b →
a__ca__c →
ea__k →
la__d →
ma__a →
a__da__b →
a__da__c →
la__k →
ma__A →
a__h(
a__f(
a__a),
a__f(
a__b))
a__h(
X,
X) →
a__g(
mark(
X),
mark(
X),
a__f(
a__k))
a__g(
d,
X,
X) →
a__Aa__f(
X) →
a__z(
mark(
X),
X)
a__z(
e,
X) →
mark(
X)
mark(
A) →
a__Amark(
a) →
a__amark(
b) →
a__bmark(
c) →
a__cmark(
d) →
a__dmark(
k) →
a__kmark(
z(
X1,
X2)) →
a__z(
mark(
X1),
X2)
mark(
f(
X)) →
a__f(
mark(
X))
mark(
h(
X1,
X2)) →
a__h(
mark(
X1),
mark(
X2))
mark(
g(
X1,
X2,
X3)) →
a__g(
mark(
X1),
mark(
X2),
mark(
X3))
mark(
e) →
emark(
l) →
lmark(
m) →
ma__A →
Aa__a →
aa__b →
ba__c →
ca__d →
da__k →
ka__z(
X1,
X2) →
z(
X1,
X2)
a__f(
X) →
f(
X)
a__h(
X1,
X2) →
h(
X1,
X2)
a__g(
X1,
X2,
X3) →
g(
X1,
X2,
X3)
Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g
Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)
The following defined symbols remain to be analysed:
a__A, a__f, mark, a__z
They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z
(11) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)
Could not prove a rewrite lemma for the defined symbol a__A.
(12) Obligation:
TRS:
Rules:
a__a →
a__ca__b →
a__ca__c →
ea__k →
la__d →
ma__a →
a__da__b →
a__da__c →
la__k →
ma__A →
a__h(
a__f(
a__a),
a__f(
a__b))
a__h(
X,
X) →
a__g(
mark(
X),
mark(
X),
a__f(
a__k))
a__g(
d,
X,
X) →
a__Aa__f(
X) →
a__z(
mark(
X),
X)
a__z(
e,
X) →
mark(
X)
mark(
A) →
a__Amark(
a) →
a__amark(
b) →
a__bmark(
c) →
a__cmark(
d) →
a__dmark(
k) →
a__kmark(
z(
X1,
X2)) →
a__z(
mark(
X1),
X2)
mark(
f(
X)) →
a__f(
mark(
X))
mark(
h(
X1,
X2)) →
a__h(
mark(
X1),
mark(
X2))
mark(
g(
X1,
X2,
X3)) →
a__g(
mark(
X1),
mark(
X2),
mark(
X3))
mark(
e) →
emark(
l) →
lmark(
m) →
ma__A →
Aa__a →
aa__b →
ba__c →
ca__d →
da__k →
ka__z(
X1,
X2) →
z(
X1,
X2)
a__f(
X) →
f(
X)
a__h(
X1,
X2) →
h(
X1,
X2)
a__g(
X1,
X2,
X3) →
g(
X1,
X2,
X3)
Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g
Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)
The following defined symbols remain to be analysed:
a__f, mark, a__z
They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z
(13) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)
Could not prove a rewrite lemma for the defined symbol a__f.
(14) Obligation:
TRS:
Rules:
a__a →
a__ca__b →
a__ca__c →
ea__k →
la__d →
ma__a →
a__da__b →
a__da__c →
la__k →
ma__A →
a__h(
a__f(
a__a),
a__f(
a__b))
a__h(
X,
X) →
a__g(
mark(
X),
mark(
X),
a__f(
a__k))
a__g(
d,
X,
X) →
a__Aa__f(
X) →
a__z(
mark(
X),
X)
a__z(
e,
X) →
mark(
X)
mark(
A) →
a__Amark(
a) →
a__amark(
b) →
a__bmark(
c) →
a__cmark(
d) →
a__dmark(
k) →
a__kmark(
z(
X1,
X2)) →
a__z(
mark(
X1),
X2)
mark(
f(
X)) →
a__f(
mark(
X))
mark(
h(
X1,
X2)) →
a__h(
mark(
X1),
mark(
X2))
mark(
g(
X1,
X2,
X3)) →
a__g(
mark(
X1),
mark(
X2),
mark(
X3))
mark(
e) →
emark(
l) →
lmark(
m) →
ma__A →
Aa__a →
aa__b →
ba__c →
ca__d →
da__k →
ka__z(
X1,
X2) →
z(
X1,
X2)
a__f(
X) →
f(
X)
a__h(
X1,
X2) →
h(
X1,
X2)
a__g(
X1,
X2,
X3) →
g(
X1,
X2,
X3)
Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g
Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)
The following defined symbols remain to be analysed:
a__z, mark
They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z
(15) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)
Could not prove a rewrite lemma for the defined symbol a__z.
(16) Obligation:
TRS:
Rules:
a__a →
a__ca__b →
a__ca__c →
ea__k →
la__d →
ma__a →
a__da__b →
a__da__c →
la__k →
ma__A →
a__h(
a__f(
a__a),
a__f(
a__b))
a__h(
X,
X) →
a__g(
mark(
X),
mark(
X),
a__f(
a__k))
a__g(
d,
X,
X) →
a__Aa__f(
X) →
a__z(
mark(
X),
X)
a__z(
e,
X) →
mark(
X)
mark(
A) →
a__Amark(
a) →
a__amark(
b) →
a__bmark(
c) →
a__cmark(
d) →
a__dmark(
k) →
a__kmark(
z(
X1,
X2)) →
a__z(
mark(
X1),
X2)
mark(
f(
X)) →
a__f(
mark(
X))
mark(
h(
X1,
X2)) →
a__h(
mark(
X1),
mark(
X2))
mark(
g(
X1,
X2,
X3)) →
a__g(
mark(
X1),
mark(
X2),
mark(
X3))
mark(
e) →
emark(
l) →
lmark(
m) →
ma__A →
Aa__a →
aa__b →
ba__c →
ca__d →
da__k →
ka__z(
X1,
X2) →
z(
X1,
X2)
a__f(
X) →
f(
X)
a__h(
X1,
X2) →
h(
X1,
X2)
a__g(
X1,
X2,
X3) →
g(
X1,
X2,
X3)
Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g
Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)
The following defined symbols remain to be analysed:
mark
They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z
(17) RewriteLemmaProof (LOWER BOUND(ID) transformation)
Proved the following rewrite lemma:
mark(
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(
n11571540_0)) →
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(
0), rt ∈ Ω(1 + n11571540
0)
Induction Base:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0)) →RΩ(1)
e
Induction Step:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(n11571540_0, 1))) →RΩ(1)
a__z(mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)), e) →IH
a__z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), e) →RΩ(1)
mark(e) →RΩ(1)
e
We have rt ∈ Ω(n1) and sz ∈ O(n). Thus, we have ircR ∈ Ω(n).
(18) Complex Obligation (BEST)
(19) Obligation:
TRS:
Rules:
a__a →
a__ca__b →
a__ca__c →
ea__k →
la__d →
ma__a →
a__da__b →
a__da__c →
la__k →
ma__A →
a__h(
a__f(
a__a),
a__f(
a__b))
a__h(
X,
X) →
a__g(
mark(
X),
mark(
X),
a__f(
a__k))
a__g(
d,
X,
X) →
a__Aa__f(
X) →
a__z(
mark(
X),
X)
a__z(
e,
X) →
mark(
X)
mark(
A) →
a__Amark(
a) →
a__amark(
b) →
a__bmark(
c) →
a__cmark(
d) →
a__dmark(
k) →
a__kmark(
z(
X1,
X2)) →
a__z(
mark(
X1),
X2)
mark(
f(
X)) →
a__f(
mark(
X))
mark(
h(
X1,
X2)) →
a__h(
mark(
X1),
mark(
X2))
mark(
g(
X1,
X2,
X3)) →
a__g(
mark(
X1),
mark(
X2),
mark(
X3))
mark(
e) →
emark(
l) →
lmark(
m) →
ma__A →
Aa__a →
aa__b →
ba__c →
ca__d →
da__k →
ka__z(
X1,
X2) →
z(
X1,
X2)
a__f(
X) →
f(
X)
a__h(
X1,
X2) →
h(
X1,
X2)
a__g(
X1,
X2,
X3) →
g(
X1,
X2,
X3)
Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g
Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)
Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)
The following defined symbols remain to be analysed:
a__h, a__A, a__f, a__g, a__z
They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z
(20) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)
Could not prove a rewrite lemma for the defined symbol a__h.
(21) Obligation:
TRS:
Rules:
a__a →
a__ca__b →
a__ca__c →
ea__k →
la__d →
ma__a →
a__da__b →
a__da__c →
la__k →
ma__A →
a__h(
a__f(
a__a),
a__f(
a__b))
a__h(
X,
X) →
a__g(
mark(
X),
mark(
X),
a__f(
a__k))
a__g(
d,
X,
X) →
a__Aa__f(
X) →
a__z(
mark(
X),
X)
a__z(
e,
X) →
mark(
X)
mark(
A) →
a__Amark(
a) →
a__amark(
b) →
a__bmark(
c) →
a__cmark(
d) →
a__dmark(
k) →
a__kmark(
z(
X1,
X2)) →
a__z(
mark(
X1),
X2)
mark(
f(
X)) →
a__f(
mark(
X))
mark(
h(
X1,
X2)) →
a__h(
mark(
X1),
mark(
X2))
mark(
g(
X1,
X2,
X3)) →
a__g(
mark(
X1),
mark(
X2),
mark(
X3))
mark(
e) →
emark(
l) →
lmark(
m) →
ma__A →
Aa__a →
aa__b →
ba__c →
ca__d →
da__k →
ka__z(
X1,
X2) →
z(
X1,
X2)
a__f(
X) →
f(
X)
a__h(
X1,
X2) →
h(
X1,
X2)
a__g(
X1,
X2,
X3) →
g(
X1,
X2,
X3)
Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g
Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)
Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)
The following defined symbols remain to be analysed:
a__g, a__A, a__f, a__z
They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z
(22) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)
Could not prove a rewrite lemma for the defined symbol a__g.
(23) Obligation:
TRS:
Rules:
a__a →
a__ca__b →
a__ca__c →
ea__k →
la__d →
ma__a →
a__da__b →
a__da__c →
la__k →
ma__A →
a__h(
a__f(
a__a),
a__f(
a__b))
a__h(
X,
X) →
a__g(
mark(
X),
mark(
X),
a__f(
a__k))
a__g(
d,
X,
X) →
a__Aa__f(
X) →
a__z(
mark(
X),
X)
a__z(
e,
X) →
mark(
X)
mark(
A) →
a__Amark(
a) →
a__amark(
b) →
a__bmark(
c) →
a__cmark(
d) →
a__dmark(
k) →
a__kmark(
z(
X1,
X2)) →
a__z(
mark(
X1),
X2)
mark(
f(
X)) →
a__f(
mark(
X))
mark(
h(
X1,
X2)) →
a__h(
mark(
X1),
mark(
X2))
mark(
g(
X1,
X2,
X3)) →
a__g(
mark(
X1),
mark(
X2),
mark(
X3))
mark(
e) →
emark(
l) →
lmark(
m) →
ma__A →
Aa__a →
aa__b →
ba__c →
ca__d →
da__k →
ka__z(
X1,
X2) →
z(
X1,
X2)
a__f(
X) →
f(
X)
a__h(
X1,
X2) →
h(
X1,
X2)
a__g(
X1,
X2,
X3) →
g(
X1,
X2,
X3)
Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g
Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)
Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)
The following defined symbols remain to be analysed:
a__A, a__f, a__z
They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z
(24) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)
Could not prove a rewrite lemma for the defined symbol a__A.
(25) Obligation:
TRS:
Rules:
a__a →
a__ca__b →
a__ca__c →
ea__k →
la__d →
ma__a →
a__da__b →
a__da__c →
la__k →
ma__A →
a__h(
a__f(
a__a),
a__f(
a__b))
a__h(
X,
X) →
a__g(
mark(
X),
mark(
X),
a__f(
a__k))
a__g(
d,
X,
X) →
a__Aa__f(
X) →
a__z(
mark(
X),
X)
a__z(
e,
X) →
mark(
X)
mark(
A) →
a__Amark(
a) →
a__amark(
b) →
a__bmark(
c) →
a__cmark(
d) →
a__dmark(
k) →
a__kmark(
z(
X1,
X2)) →
a__z(
mark(
X1),
X2)
mark(
f(
X)) →
a__f(
mark(
X))
mark(
h(
X1,
X2)) →
a__h(
mark(
X1),
mark(
X2))
mark(
g(
X1,
X2,
X3)) →
a__g(
mark(
X1),
mark(
X2),
mark(
X3))
mark(
e) →
emark(
l) →
lmark(
m) →
ma__A →
Aa__a →
aa__b →
ba__c →
ca__d →
da__k →
ka__z(
X1,
X2) →
z(
X1,
X2)
a__f(
X) →
f(
X)
a__h(
X1,
X2) →
h(
X1,
X2)
a__g(
X1,
X2,
X3) →
g(
X1,
X2,
X3)
Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g
Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)
Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)
The following defined symbols remain to be analysed:
a__f, a__z
They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z
(26) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)
Could not prove a rewrite lemma for the defined symbol a__f.
(27) Obligation:
TRS:
Rules:
a__a →
a__ca__b →
a__ca__c →
ea__k →
la__d →
ma__a →
a__da__b →
a__da__c →
la__k →
ma__A →
a__h(
a__f(
a__a),
a__f(
a__b))
a__h(
X,
X) →
a__g(
mark(
X),
mark(
X),
a__f(
a__k))
a__g(
d,
X,
X) →
a__Aa__f(
X) →
a__z(
mark(
X),
X)
a__z(
e,
X) →
mark(
X)
mark(
A) →
a__Amark(
a) →
a__amark(
b) →
a__bmark(
c) →
a__cmark(
d) →
a__dmark(
k) →
a__kmark(
z(
X1,
X2)) →
a__z(
mark(
X1),
X2)
mark(
f(
X)) →
a__f(
mark(
X))
mark(
h(
X1,
X2)) →
a__h(
mark(
X1),
mark(
X2))
mark(
g(
X1,
X2,
X3)) →
a__g(
mark(
X1),
mark(
X2),
mark(
X3))
mark(
e) →
emark(
l) →
lmark(
m) →
ma__A →
Aa__a →
aa__b →
ba__c →
ca__d →
da__k →
ka__z(
X1,
X2) →
z(
X1,
X2)
a__f(
X) →
f(
X)
a__h(
X1,
X2) →
h(
X1,
X2)
a__g(
X1,
X2,
X3) →
g(
X1,
X2,
X3)
Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g
Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)
Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)
The following defined symbols remain to be analysed:
a__z
They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z
(28) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)
Could not prove a rewrite lemma for the defined symbol a__z.
(29) Obligation:
TRS:
Rules:
a__a →
a__ca__b →
a__ca__c →
ea__k →
la__d →
ma__a →
a__da__b →
a__da__c →
la__k →
ma__A →
a__h(
a__f(
a__a),
a__f(
a__b))
a__h(
X,
X) →
a__g(
mark(
X),
mark(
X),
a__f(
a__k))
a__g(
d,
X,
X) →
a__Aa__f(
X) →
a__z(
mark(
X),
X)
a__z(
e,
X) →
mark(
X)
mark(
A) →
a__Amark(
a) →
a__amark(
b) →
a__bmark(
c) →
a__cmark(
d) →
a__dmark(
k) →
a__kmark(
z(
X1,
X2)) →
a__z(
mark(
X1),
X2)
mark(
f(
X)) →
a__f(
mark(
X))
mark(
h(
X1,
X2)) →
a__h(
mark(
X1),
mark(
X2))
mark(
g(
X1,
X2,
X3)) →
a__g(
mark(
X1),
mark(
X2),
mark(
X3))
mark(
e) →
emark(
l) →
lmark(
m) →
ma__A →
Aa__a →
aa__b →
ba__c →
ca__d →
da__k →
ka__z(
X1,
X2) →
z(
X1,
X2)
a__f(
X) →
f(
X)
a__h(
X1,
X2) →
h(
X1,
X2)
a__g(
X1,
X2,
X3) →
g(
X1,
X2,
X3)
Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g
Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)
Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)
No more defined symbols left to analyse.
(30) LowerBoundsProof (EQUIVALENT transformation)
The lowerbound Ω(n1) was proven with the following lemma:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)
(31) BOUNDS(n^1, INF)
(32) Obligation:
TRS:
Rules:
a__a →
a__ca__b →
a__ca__c →
ea__k →
la__d →
ma__a →
a__da__b →
a__da__c →
la__k →
ma__A →
a__h(
a__f(
a__a),
a__f(
a__b))
a__h(
X,
X) →
a__g(
mark(
X),
mark(
X),
a__f(
a__k))
a__g(
d,
X,
X) →
a__Aa__f(
X) →
a__z(
mark(
X),
X)
a__z(
e,
X) →
mark(
X)
mark(
A) →
a__Amark(
a) →
a__amark(
b) →
a__bmark(
c) →
a__cmark(
d) →
a__dmark(
k) →
a__kmark(
z(
X1,
X2)) →
a__z(
mark(
X1),
X2)
mark(
f(
X)) →
a__f(
mark(
X))
mark(
h(
X1,
X2)) →
a__h(
mark(
X1),
mark(
X2))
mark(
g(
X1,
X2,
X3)) →
a__g(
mark(
X1),
mark(
X2),
mark(
X3))
mark(
e) →
emark(
l) →
lmark(
m) →
ma__A →
Aa__a →
aa__b →
ba__c →
ca__d →
da__k →
ka__z(
X1,
X2) →
z(
X1,
X2)
a__f(
X) →
f(
X)
a__h(
X1,
X2) →
h(
X1,
X2)
a__g(
X1,
X2,
X3) →
g(
X1,
X2,
X3)
Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g
Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)
Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)
No more defined symbols left to analyse.
(33) LowerBoundsProof (EQUIVALENT transformation)
The lowerbound Ω(n1) was proven with the following lemma:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)
(34) BOUNDS(n^1, INF)